package com.ljy.my_study.lintcode.前K大数;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

/**
 * @author James
 * @date 2018年10月11日
 */
public class Solution {
	private int k;

	private PriorityQueue<Integer> queue=null;
	private Comparator<Integer> c=null;
	
	/*
	 * @param k: An integer
	 */
	public Solution(int k) {
		this.k=k;
		c=new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				return o2-o1;
			}
		};
		queue=new PriorityQueue<>();
	}

	/*
	 * @param num: Number to be added
	 * 
	 * @return: nothing
	 */
	public void add(int num) {
		queue.add(num);
		if(queue.size()>k) {
			queue.poll();
		}
	}

	/*
	 * @return: Top k element
	 */
	public List<Integer> topk() {
		List<Integer> list=new ArrayList<>();
		PriorityQueue<Integer> newQueue=new PriorityQueue<>();
		Integer val=null;
		while((val=queue.poll())!=null) {
			newQueue.add(val);
			list.add(val);
		}
		queue=newQueue;
		Collections.sort(list,c);
		System.out.println(list);
		return list;
	}
	
	public static void main(String[] args) {
		Solution s=new Solution(3);
		s.add(3);
		s.add(10);
		s.topk();
		s.add(1000);
		s.add(-99);
		s.topk();
		s.add(4);
		s.topk();
		s.add(100);
		s.topk();

	}
}
